package main.Q201_300;

import java.util.*;

public class Q231_240 {
    public static void main(String[] args) {
        System.out.println("Question231：2的幂");
        System.out.println("Question232：用栈实现队列");
        System.out.println("Question233：");
        System.out.println("Question234：回文链表");
        System.out.println("Question235：二叉搜索树的最近公共祖先");
        System.out.println("Question236：二叉树的最近公共祖先");
        System.out.println("Question237：删除链表中的节点");
        System.out.println("Question238：除自身以外数组的乘积");
        System.out.println("Question239：滑动窗口最大值");
        System.out.println("Question240：搜索二维矩阵Ⅱ");
    }
}

class Question231{
    public boolean isPowerOfTwo(int n) {
        boolean flag=true;
        while (n>=2){
            if (n%2!=0) {
                flag=false;
                break;
            }
            n=n/2;
        }
        if (n<=0) flag=false;
        return flag;
    }
}

class Question232{
    Stack<Integer> major,assist;
    public Question232() {
        major=new Stack<>();
        assist=new Stack<>();
    }

    public void push(int x) {
        major.add(x);
    }

    public int pop() {
        while (major.size()>1){
            assist.add(major.pop());
        }
        int top=major.pop();
        while (!assist.isEmpty()){
            major.add(assist.pop());
        }
        return top;
    }

    public int peek() {
        while (major.size()>1){
            assist.add(major.pop());
        }
        int top=major.peek();
        while (!assist.isEmpty()){
            major.add(assist.pop());
        }
        return top;
    }

    public boolean empty() {
        return major.isEmpty();
    }
}

class Question234{
    public boolean isPalindrome(ListNode head) {
        StringBuffer str=new StringBuffer();
        while (head!=null){
            str.append(head.val);
            head=head.next;
        }
        return str.toString().equals(new StringBuffer(str.toString()).reverse().toString());
    }
//    public boolean isPalindrome(ListNode head) {
//        List<Integer> list=new ArrayList<>();
//        while (head!=null){
//            list.add(head.val);
//            head=head.next;
//        }
//        Integer[] arr=list.toArray(new Integer[0]);
//        int length= arr.length;
//        for (int i=0;i< length/2;i++){
//            if (arr[i]!=arr[length-1-i]) return false;
//        }
//        return true;
//    }
}

class Question235{
    public class Info{
        public boolean isExistNode1;
        public boolean isExistNode2;
        public TreeNode commonFather;
        public Info(boolean isExistNode1,boolean isExistNode2,TreeNode commonFather){
            this.isExistNode1=isExistNode1;
            this.isExistNode2=isExistNode2;
            this.commonFather=commonFather;
        }
    }
    public Info process(TreeNode root,TreeNode p,TreeNode q){
        if (root==null) return new Info(false,false,null);
        Info left=process(root.left, p, q);//左子树信息
        Info right=process(root.right, p, q);//右子树信息
        if (left.commonFather!=null||right.commonFather!=null){//其中一个子树中已经存在公共祖先
            return left.commonFather==null ? right : left;//将存在公共祖先的子树信息返回
        }
        boolean node1=false,node2=false;
        TreeNode temp=null;
        if (root==p|| left.isExistNode1==true || right.isExistNode1==true) node1=true;//当其中一个子树中存在p或当前节点为p
        if (root==q|| left.isExistNode2==true || right.isExistNode2==true) node2=true;//当其中一个子树中存在q或当前节点为q
        if (node1&&node2){//当本节点即为公共祖先时
            temp=root;
        }
        return new Info(node1,node2,temp);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).commonFather;
    }
}

class Question236{
    public class Info{
        public boolean isExistNode1;
        public boolean isExistNode2;
        public TreeNode commonFather;
        public Info(boolean isExistNode1,boolean isExistNode2,TreeNode commonFather){
            this.isExistNode1=isExistNode1;
            this.isExistNode2=isExistNode2;
            this.commonFather=commonFather;
        }
    }
    public Info process(TreeNode root,TreeNode p,TreeNode q){
        if (root==null) return new Info(false,false,null);
        Info left=process(root.left, p, q);//左子树信息
        Info right=process(root.right, p, q);//右子树信息
        if (left.commonFather!=null||right.commonFather!=null){//其中一个子树中已经存在公共祖先
            return left.commonFather==null ? right : left;//将存在公共祖先的子树信息返回
        }
        boolean node1=false,node2=false;
        TreeNode temp=null;
        if (root==p|| left.isExistNode1==true || right.isExistNode1==true) node1=true;//当其中一个子树中存在p或当前节点为p
        if (root==q|| left.isExistNode2==true || right.isExistNode2==true) node2=true;//当其中一个子树中存在q或当前节点为q
        if (node1&&node2){//当本节点即为公共祖先时
            temp=root;
        }
        return new Info(node1,node2,temp);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).commonFather;
    }
}

class Question237{
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

class Question238{
    public int[] productExceptSelf(int[] nums) {
        int[] result=new int[nums.length];
        result[0]=1;
        for(int i=1;i<nums.length;i++) {// 前缀乘积
            result[i]=result[i-1]*nums[i-1];
        }
        int right=1;
        for(int i=nums.length-1;i>=0;i--) {// 后缀乘积
            result[i]=result[i]*right;
            right=right*nums[i];
        }
        return result;
    }
//    public int[] productExceptSelf(int[] nums) {
//        int length= nums.length;
//        int[] leftMulti=new int[length],rightMulti=new int[length],result=new int[length];
//        for (int i=0;i<length;i++){
//            if (i==0) leftMulti[0]=1;//第0个左侧累乘为1
//            else leftMulti[i]=leftMulti[i-1]*nums[i-1];//第i个左侧累乘为i-1的累乘*i-1的元素
//        }
//        for (int i=length-1;i>=0;i--){
//            if (i==length-1) rightMulti[length-1]=1;//第length-1个右侧累乘为1
//            else rightMulti[i]=rightMulti[i+1]*nums[i+1];//第i个右侧累乘为i+1的累乘*i+1的元素
//        }
//        for (int i=0;i<length;i++){
//            result[i]=leftMulti[i]*rightMulti[i];//左侧累乘*右侧累乘
//        }
//        return result;
//    }
}

class Question239{
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) deque.pollLast();
            deque.offerLast(i);
        }
        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) deque.pollLast();
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) deque.pollFirst();
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

class Question240{
    public boolean searchMatrix(int[][] matrix, int target) {
        int col=matrix[0].length;
        for (int i=0;i< matrix.length;i++){
            if (matrix[i][0]<=target&&matrix[i][col-1]>=target){
                int index=search(matrix[i],target);
                if (index>=0) return true;
            }
        }
        return false;
    }
    public int search(int[] nums,int target){
        int left=0,right= nums.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            int num=nums[mid];
            if (num==target) return mid;
            else if (num>target) right=mid-1;
            else left=mid+1;
        }
        return -1;
    }
}